vector_and_list

2022/3/10

Vector 和 List

vector和list都是标准库中的容器

vector是动态数组，拥有一段连续的内存空间，优点在于可以用下标访问，访问效率高。但也正是因为这个原因，导致它在删除和插入时效率不高。

list是双向链表，内存空间是不连续的，所以访问效率不高，但是对于链表来说，插入和删除只需要移动指针指向，故它的删除和插入效率高。

最近项目开发有用到，这里记录一下一些需要注意的问题

删除元素

vector和list删除元素的方法都一样，这里以list为例

由于删除过程中有可能涉及迭代失效，这里记录一下

删除主要是用到erase，他的返回值是当前被删除元素的下一个元素的迭代器

所以我们可以在删除元素的时候顺便用其返回值赋给迭代器

没有删除元素时迭代器需要自增，删除元素时迭代器不需要自增

假设我们的需求是在容器中删除值为2，3，5的数，我们可以这样写

std::list<int> list1{1,2,2,2,3,4,5,6,7};

for(auto iter = list1.begin();iter!=list1.end();)
{
    if(*iter == 2 || *iter == 3 || *iter == 5)
    {
        iter = list1.erase(iter);
        continue;
    }
    else
    {
        iter ++;
    }        
}

但是如果有多个判断而且判断条件很长的话这样子写很不优雅所以可以写成这样

std::list<int> list1{1,2,2,2,3,4,5,6,7};

for(auto iter = list1.begin();iter!=list1.end();)
{
    if(*iter == 2)
    {
        iter = list1.erase(iter);
        continue;
    }

    if(*iter == 3)
    {
        iter = list1.erase(iter);
        continue;
    }

    if(*iter == 5)
    {
        iter = list1.erase(iter);
        continue;
    }
    iter ++;
}

虽然看起来多此一举但是我感觉这样写更有条理

遍历元素过程中往尾部插入元素

我们常常会需要往一个容器里加入元素，

对于vector和list来说，都可以使用push_back

但是如果不注意的话，很有可能导致死循环

即一边不断加入，一边又不断迭代下去

而最常规的想法就是在循环之前，就先记录下迭代的终点

假设我们的需求是迭代过程中不断往容器中加入数字2

并打印当前迭代处的元素（表示我们能访问到）

但是只循环原容器部分，即后面加入的数字2部分不循环

vector

vector最方便就是下标访问

很容易就可以实现

std::vector<int> vec1{1, 2, 3, 4, 5, 6, 7, 8};
int end_index = vec1.size();
for (int i = 0; i < end_index; i++)
{
    vec1.push_back(2);
    std::cout << vec1[i] << std::endl;
}

注意 vector不能使用迭代器边迭代边push_back

因为vector的扩容，是另外起一片内存，然后再把数据拷贝过去，

所以push_back之后迭代器位置会错误

list

list的话自然而然的想法就是用迭代器

std::list<int> list1{1, 2, 3, 4, 5, 6, 7, 8};
auto end_ptr = list1.end();
for (auto iter = list1.begin(); iter!=end_ptr; iter++)
{     
    list1.push_back(2);
    std::cout << *iter << std::endl;
}

但是上述代码会死循环

根据链表的性质，虽然end不变，但是随着你插入元素，你的节点越来越多，一直走不到end

所以要记录一下原来的容器的大小，限制迭代次数，如下